package com.mrzhou.study.struct.sort;

import com.mrzhou.core.tool.utils.DataUtil;

/**
 * 排序算法之选择排序
 *  算法思路:
 *      它的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值，与 arr[0]交换，
 *      第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，
 *      第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2]交换，…，
 *      第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…,
 *      第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，
 *      总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。
 */
public class SelectSort {

    public static void main(String[] args) {
        int arr[] = new int[90000];
        for(int i = 0; i < arr.length; i++) {
            arr[i] = DataUtil.randomInt(0, arr.length);
        }
        Long startTime = System.currentTimeMillis();
        SelectSort.sort(arr);
        Long endTime = System.currentTimeMillis();
        System.out.println(SelectSort.toString(arr, 20));
        System.out.printf("选择排序[%d]条数据, 花费的时间: %d\n", arr.length, (endTime - startTime));
    }

    public static void sort(int arr[]) {
        for(int i = 0; i < arr.length - 1; i++) {
            int temp = arr[i];
            int index = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(temp < arr[j]) {
                    temp = arr[j];
                    index = j;
                }
            }
            arr[index] = arr[i];
            arr[i] = temp;
        }
    }

    public static String toString(int[] arr, int size) {
        StringBuffer sb = new StringBuffer("[");
        for (int i = 0; i < arr.length; i++) {
            if(i%size == 0 && i != 0 && i != arr.length - 1) {
                sb.append("\n");
            }
            if(i == arr.length - 1) {
                sb.append(arr[i]);
            } else {
                sb.append(arr[i]).append(", ");
            }
        }
        return sb.append("]").toString();
    }

}
